


\section{数据结构问题举例}
\subsection{简洁实现升序链表插入}
链表插入的繁琐之处在于，要判断头指针是否为空，以及是否需要更新头指针(头前插)。
通过哨兵(存放上限值，\cite{pp}13.2)使得链表至少有一个元素，无需检查head是否为空。
通过使用指向指针的指针(\cite{pp}13.6.4)，避免区分头前和头后插入两种情况。
\begin{verbatim}
for(pp=&head;(*pp)->val<t;pp=&((*pp))->next);
if (*pp)->val &=& t:return; 
*pp=new node(val=t, next=*pp);
\end{verbatim}
\label{problem:listInsert}。

\subsection{简洁实现BST插入}
通过哨兵(存放待搜索值)和指向指针的指针(\cite{pp}13.6.7)，使得BST至少有一个元素，且无需单独判断是否需要更新root指针的值。
\begin{verbatim}
sentinel->val=t;
for(pp=&root;(*pp)->val!=t;pp=(t<(*pp)->val)?(&((*pp)->left)):(&((*pp)->right)));
if *pp&=& sentinel:*pp=new node(val=t, left=right=sentinel);
\end{verbatim}
\label{problem:BSTInsert}。


\subsection{m个互异整数搜索结构}
\cite{pp}13介绍了有序数组，有序链表，BST，位向量，桶。
链表相对于数组，适用于待存放元素个数不明确的情形。虽然链表在插入数据时不需要移动数据，但其内存访问不连续且需要额外空间存放指针，对cache不友好，性能甚至不如数组。对于纯搜索过程，有序数组可以在log时间内完成，链表需要线性时间。桶实质是一种散列结构，用链表处理碰撞。


\subsection{实现快速返回最大值的队列}
\cite{bop}3.7。
方法零：按照传统方式，以数组或链表存储队列，两个指针指向头尾。MaxVal操作复杂度为$O(N)$,增、删复杂度为常数。个人认为可以保存最大值，增删是予以更新，Enqueue的复杂度为常数, dequeue复杂度线性, MaxVal复杂度为常数。方法一：使用堆。Enqueue和Dequeue为$O(logN)$, MaxVal为常数。类似于\cite{ita}中的优先级队列。方法二：\cite{bop}提出了一种$O(1)$时间MaxVal操作的栈结构，用链表连接不同状态时的最大值，并用两个这种栈串联实现了队列。


\subsection{有序文件多路归并}
\cite{pp}14.6.4.d。用堆(优先级队列)表示每个文件的下一个元素。从堆中选出最小元素，再从对应文件中补上。

\subsection{二叉树中最远节点}
\cite{bop}3.8。
经分析可知，最远两节点有两种情况：两个叶子节点；根节点和一个叶子节点，此时根结点左右子树其一必为空。总之，为某子树(或本树)左右子树最大高度之和(叶子结点高度为1)。可深度优先遍历，检查以各结点为根结点的子树的左右子树的高度之和，更新当前最优解。书上使用的是递归方法，要求自作非递归法。

\subsection{分层遍历二叉树}
\cite{bop}3.10。有两问。第一问是打印某一层结点。第二问是从上到下分层打印各结点，层内从左到右。扩展题是从下到上分层打印各结点，层内从左到右或从右到左。对于第一问，按照正常流程遍历树，判断层数合适则打印。其他问题，使用一个数组，将根结点压入，遍历数组，同时按照一定规则将各结点压入数组末尾。最终数组中元素排列符合要求。此题比较简单。


\subsection{实现快速返回最大值的队列}
\cite{bop}3.7。
方法零：按照传统方式，以数组或链表存储队列，两个指针指向头尾。MaxVal操作复杂度为$O(N)$,增、删复杂度为常数。个人认为可以保存最大值，增删是予以更新，Enqueue的复杂度为常数, dequeue复杂度线性, MaxVal复杂度为常数。方法一：使用堆。Enqueue和Dequeue为$O(logN)$, MaxVal为常数。类似于\cite{ita}中的优先级队列。方法二：\cite{bop}提出了一种$O(1)$时间MaxVal操作的栈结构，用链表连接不同状态时的最大值，并用两个这种栈串联实现了队列。

\subsection{二叉树中最远节点}
\cite{bop}3.8。
经分析可知，最远两节点有两种情况：两个叶子节点；根节点和一个叶子节点，此时根结点左右子树其一必为空。总之，为某子树(或本树)左右子树最大高度之和(叶子结点高度为1)。可深度优先遍历，检查以各结点为根结点的子树的左右子树的高度之和，更新当前最优解。书上使用的是递归方法，要求自作非递归法。

\subsection{分层遍历二叉树}
\cite{bop}3.10。有两问。第一问是打印某一层结点。第二问是从上到下分层打印各结点，层内从左到右。扩展题是从下到上分层打印各结点，层内从左到右或从右到左。对于第一问，按照正常流程遍历树，判断层数合适则打印。其他问题，使用一个数组，将根结点压入，遍历数组，同时按照一定规则将各结点压入数组末尾。最终数组中元素排列符合要求。此题比较简单。



\subsection{稀疏矩阵存储}
\cite{pp}10.2提出用数组表示各列，指向行链表。同时提出如果编程语言不支持指针，可以把所有行依次相连为单一大数组，用另一个数组表示各列首元素在大数组中的位置。\cite{pp}10.6.2提出，依此按照x、y坐标排列各元素，以支持二分搜索。对于其他空间节省技术，经常是通过仅存储差量来实现,r如\cite{pp}10.6.4,10.6.5。
\label{problem:sparseMatrix}


\section{数据分析问题举例}

\subsection{数组中最大的K个数}
参\cite{bop}2.5, \cite{ita}9.2-9.3(\cite{ita}称找到第k小的数为kth order statistics)。
方法零：全部排序，$O(NlogN)$， 适用于多次查询场景;或只对前k个数部分排序，$O(nk)$，可使用利用选择或交换的排序算法\cite{subsec:sortAthmClass}。
方法一：随机分割保留单侧。\cite{ita}9.2称之为RANDOMIZED-SELECT算法, \cite{pp}11.5.9和\cite{wikipedia}称之为选择算法。期望运行时间为线性，最差为平方时间。\cite{ita}9.3的SELECT算法通过精心挑选pivot来确保最差时间也为线性。涉及随机访问，不适合外存储操作。\cite{bop}2.5.3认为线性算法常数项太大，未必好。
方法二：值域二分查找。每次迭代需要线性时间,迭代次数为$log_{2}(V_{max}-V_{min}/\delta)$，$\delta$为元素间最小间隔(对于整数，$\delta$为1)。对于均匀分布的数据，总时间为NlogN。文件操作优化(\cite{bop}2.5.3):每次迭代，将当期搜索区间的样本复制到新的文件中(\cite{self}:磁盘可能频繁换道，但适合于两个磁盘或磁带，参\ref{subsec:dupNumberInFile})，当区间内的样本数能够全部载入内存时，则不需要再进行文件操作。\cite{self}认为，为减少磁盘换道，对文件的读取采用搅拌式。
方法三：前K个元素生成容量为K的大顶堆，从第K+1个元素开始遍历，更新堆的内容。时间为$O(NlogK)$适合外存储操作。如果K个数可以全部载入内存，则只遍历文件一遍，不涉及随机访问。如果K也很大，需要将k分割为多个可以载入内存的部分(\cite{bop}2.5.4)。
\label{subsec:orderStatistics}

方法四：如果值域有限且非常小，计数排序(\cite{bop}2.5.5)。
\subsection{找到数组中最大数和最小数}
\cite{bop}2.10。如分别独立找到最大值和最小值，需要2N次比较。其他方法可以达到1.5N次比较。
方法一：每邻近的一对数为一组，组内比较，较小者调整到奇数位置。进而分别在奇数位置和偶数位置寻找最小和最大。
方法二：每邻近的一对数为一组，遍历每个组，每组内用3次比较更新当前的最大值和最小值。
方法三：分治法。
其时间复杂度见:\ref{divide_complex}。


\subsection{求众数和绝对众数}
求众数(Mode):
\cite{pp}11.5.1。
方法1:基于选择算法，参考\ref{subsec:orderStatistics}，取轴值x, 根据快排的过程，小于x的放在左边，大于x的放在右边。同时统计x的出现次数T。 如果x左边的个数（不算X）多于T，向左递归；同理，如果x右边的个数对于T，向右递归。复杂度为$O(nlogn)$。
方法2:基于分布的统计，利用数组(如果数据取值范围为有限区间内的整数)或散列。时间复杂度为线性，空间复杂度较高。
方法3:先排序。复杂度主要来自排序操作。

求绝对众数：
\cite{bop}2.3,发帖水王问题。
方法：不断去除相异的两个值。
扩展为有三个ID，各自超过ID出现次数的四分之一。

\subsection{数组相邻差值最大值}
\cite{bop}2.11扩展1\\
所述相邻指值的相邻，并非数组中位置的相邻。
根据抽屉原理，相邻差值的最大值应不小于delta=(Vmax-Vmin)/(N-1)。将取值域分解为长为delta的若干桶，每隔桶内不会有我们希望的值。记录每个桶的最大值和最小值，然后遍历所有的桶即可。时间和空间复杂度都是线性。



\subsection{找出数组中和为给定值S的两个数}
\cite{bop}2.12, \cite{ms100}14\\
方法一：排序，对数组中每个数A，用二分法查找S-A是否在数组中。$O(NlogN)$。方法二：建立Hash表，使得用$O(1)$时间即可求出某个值是否在数组中，对数组中每个数A，查找S-A是否在数组中。时间与空间复杂度均为线性。方法三：双下标相向游动.先排序，然后从数组的头和尾分别寻找一个数，使其和为S。查找时间为线性。书中提到，很多题目要求返回两个数组下标的，适用类似方法，即在一个循环体里用两个变量反向遍历。

\subsection{子向量最大和}
\cite{bop}2.14, \cite{pp}第8章整章讲述该问题。\label{problem:maxsubvector}\\
方法零：枚举所有子向量$O(N^2)$，计算其和, 总时间$O(N^3)$。若将求和与枚举操作的第二个循环合并，或者预先计算累加数组，总时间$O(N^2)$。方法二:分治法，分别在两个砍半数组中求解局部最优，再求解跨界解，给定两个序列头部，分别向前、向后搜索合适的子数组尾部。总时间$O(NlgN)$。方法三：动态规划，寥寥数行代码，线性时间复杂度。遍历数组，更新已遍历部分以当前位置为结尾的最优解，和已遍历部分最优解，后者的更新依赖于前者。方法四：\cite{self}为便于理解方法三而创，全局最优解必为以某i为结尾的子数组，先用线性的时间和空间求出以各i为结束的子数组的最大值序列maxEnd[i]，maxEnd[k]依赖于maxEnd[k-1]。再用线性时间找到maxEnd[i]数组中的最大值即可。方法五:线性时间分治法\cite{pp}8.7.8。分别在两个砍半数组中求出局部最优和跨界最优，则总的跨界最优借即为两个砍半数组跨界最优解之和。
\label{subsec:maxsubsum}

\subsection{总和最接近0的子向量}
\cite{pp}8.7.10，是\ref{problem:maxsubvector}的延伸。使用累加数组，$cum[-1]=0,cum[i]=\sum_{k=0}^{k=i}{x[i]}$，转化为求cum[n]中最接近元素的问题。可以在$O(NlogN)$时间内通过排序来完成。似乎可以仿照原题对动态规划算法，将评价指标更改即可。\label{problem:zerosubvec}

\subsection{总和最接近常数t的子向量}
\cite{pp}8.7.10，是\ref{problem:maxsubvector}的延伸。书上未给出答案。如果仿照\ref{problem:zerosubvec}使用累加数组，转化为求cum[n]中差值最接近t的问题。可以在$O(NlogN)$时间完成排序，通过$O(NlogN)$时间在有序数组中完成查找。似乎可以仿照原题对动态规划算法，将评价指标更改即可。

\subsection{环形数组子向量最大和}
\cite{bop}2.14扩展1\\
将解空间分为两部分，一部分不过尾，参考\ref{subsec:maxsubsum}。另一部分过尾。过尾者，分别从头和尾按照两个方向求出最优子序列。书上如此似乎未能妥善处理两个最优子序列重叠的情况。我认为应该求出数组总和，减去子向量长度最小值。

\label{subsec:maxroundsubsum}

\subsection{二维数组子向量最大和}
\cite{bop}2.15\\
方法零：枚举，$O(N^2 \cdot M^2) \cdot \textrm{二维求和复杂度}$，通过部分和缓存方法，可以将二维求和复杂度做到$O(1)$。所谓部分和就是从某元素到原点的连线为对角线的矩形区域进行求和。方法二：只在Y维度进行枚举，确定上下边，按照一维的方法(参\ref{subsec:maxsubsum}）确定左右边，求出子数组之和，$O(NM \cdot min(N,M))$。按照这两种方法，可以将问题扩展为三维、四维。参考\ref{subsec:maxroundsubsum} ，可以求解首位相连情形。


\subsection{最长递增子序列}
\begin{verbatim}
http://en.wikipedia.org/wiki/Longest_increasing_subsequence
\end{verbatim}
\cite{bop}2.16\\
同\ref{subsec:maxsubsum}节不同，此处序列不必连续。
此题如使用枚举方法，子序列共有$2^N$个，不合适。方法一：动态规划，记LIS[i]为以i为末尾的最长递增子序列(书上说是前i个元素中的最长子序列)，至少为1。$LIS[i]=max\{1,LIS[k]\}, k<i, array[k]<array[i]$。最终返回$max{LIS[i]}$,时间复杂度为$O{N^2}$,需存储LIS数组。方法二：动态规划，遍历数组，存储$TAIL[j]$为当前(在遍历过程中更新)时刻所有长度为j的递增序列的尾值的最小值，MAXL为当前的最长递增序列，利用TAIL计算LIS，$j \gets MAXL to 1$, 如某j满足TAIL[j]小于array[i]，则$LIS[i] \gets j+1$。同时，可能会更新TAIL[j+1]，MAXL。时间复杂度$O{N^2}$。方法三：思路同方法二，但在选取j时，从LIS[i-1]开始，并使用二分查找。利用了TAIL为递增数组，及$LIS[i] \le LIS[i-1]+1$。本节及\ref{subsec:maxsubsum}启发我们，数组不仅可看作静态的数据集合，也可看作一个更大的动态增长的数据集的组成部分。

\subsection{数组均匀分割}
\cite{bop}2.18,要求长度为2N的数组分成两个长度为N的数组，且和最接近\\记数组为array[k], 和的一半为S。
方法零：枚举法的复杂度$\left( \begin{array}{c} N \\ 2N \end{array} \right) = \frac{(2N)!}{N!N!}$，找出最接近S的组合。书上未提及此法。
    方法一：动态规划，遍历k，更新集合类$V_i，i \le k, V_i$表示任意i个元素的和的可取值。最终研究$V_N$中的最优值。书中未提及如何据此找到对应分配方案。可能需要在$V_i$中添加附加信息。方法二：如果取值域很小，用boolean数组isOK[i][s]表示是否能存在i个变量其和为s。三维遍历k,i,s, $i \le N，i \le k, s \le S$, 如果isOk[i-1][s-array[k]]为真，则isOk[i][s]为真。



\subsection{坐标系中最近点对}
\cite{bop}2.11\\
方法零：枚举，$O(N^2)$;方法一：按X坐标分治，$O(N^2)$;方法二：按X坐标分治，求出不跨界的最近点对的距离为L;探索跨界点对距离时，范围缩小至距界线不超过L的范围，由此进行枚举，总复杂度仍为$O(N^2)$。跨界最近点对必处于Y方向距离小于L的带状区内(面积$2L^2$)，且区内点数不超过8,左右半区点数各不超过4，则最近点对在Y方向间的点不会超过6个。书上说用$O(N)$时间完成对所有带状区内最近点对的查找，总时间$O(NlgN)$，具体方法不明。如果在X方向上2L区域内对点按Y值排序，$O(lgN)$，则总时间$O(Nlg^{2}N)$，比枚举法有进步。
扩展题2要求坐标系中最远点对，不解。

\subsection{目标区间是否包含于源区间并集}
\cite{bop}2.19\\
先对源区间进行排序$O(NlogN)$和合并$O(N)$，此后，目标区间包含于源区间并集当且仅当目标区间包含于某个源区间。如果目标区间反包含某源区间，或同某源区间交叠，均不成立。

\subsection{丢失的备份}
\cite{bop}1.5。每个结点都冗余备份为2份，因此活跃ID列表中每个ID会出现两次，但一些结点可能会失效，其ID不出现于列表。在已知有1个/2个结点出故障的情况下，找到其ID。如果只有1个ID失效，将所有活跃的ID相异或，将得到失效ID。如果两个ID失效，事先应计算好所有ID总和，减去活跃ID总和，可以得到一个方程。另一个方程可以基于所有ID的乘积、平方和、异或等。
\subsection{缺失的整数}
\cite{pp}2.1A，文件中包含不足40亿个32位整数(32位整数有42.9亿种取值)，要求找到一个缺失的整数。如果内存无法容纳位图(32位整数需要512MB的位图空间)，可以在值域二分搜索，每次迭代将当前值域的样本复制到另一个文件上，空域空间因小于值域空间，因此空域能保证缩半。如果题目条件是所有32bit整数中只缺1个，可以异或。因为所有整数异或为0。参\ref{subsec:dupNumberInFile}。

\subsection{至少出现两次的整数}
\cite{pp}2.6.2，文件中包含多于43亿个32位整数(32位整数有42.9亿种取值)，要求找到一个重复的整数。如果内存无法容纳位图(32位整数需要512MB的位图空间)，可以在值域二分搜索，即查找小于中间值的数值是否冗余，然后值域缩半。每次迭代将当前值域的样本复制到另一个工作磁带上，但空域空间大于值域空间，不能保证空域缩半，因此最差情况下复杂度为$NlogN$。优化:(\cite{pp}2.6.2 Jim Saxe)，如果值域容量为m，则只复制m+1个样本，保证空域缩半。另外(\cite{self}, 参\ref{subsec:orderStatistics}),当m足够小时，开始使用位图法或全部载入内存。另外(\cite{self})，即使空域不缩半，如果每次迭代都将空域按一个线性因子缩小，则平均时间也为线性(无限项等比级数之和)。当发现当前值域空间存在冗余时，即可丢弃当前空域位置之后的位置。这样，不需要复制额外的文件，只要更新文件搜索范围即可。进一步，对文件的访问可以采用搅拌式。

\label{subsec:dupNumberInFile}

\subsection{约瑟夫环问题}
\cite{ms100}18,\cite{sword}45。圈有n个结点，击鼓传花式不断删除第m个结点。记该问题为f(n,m)，有 $f(n,m)=[f(n-1,m)+m]\bmod n$




\section{进制表示问题举例}
本节中的问题涉及非常大的数字，普通内置数据类型容易溢出，应自定义BigInt类型。
\subsection{N!十进制/二进制中末尾的0个数}
\cite{bop}2.2。\\
对于十进制，0的个数等于所有质因子中5的个数。每隔5,产生一个因子5;每隔25,又产生一个因子5；每隔125,625,\ldots,
对于二进制，类似。另外N！中质因子2的个数等于N-N的二进制表示中1的个数。
\subsection{选择M，使N*M只包含0和1}
\cite{bop}2.8。\\转化为选择符合条件的K，使得K整除N。遍历K，值域按照模划分为N份，每份只保留最小者。K从i位数变成i+1位，相当于用$10^i$加上已访问的所有数，那么，i+1位数模N的结果依次为$10^i mod N$加上已访问的数$mod N$的和再模N。直到mod值为零的集合不再为空。遍历结束的条件，书上提到循环节的概念，不甚明了。

\subsection{Hamming Weight(Population Count)}
\cite{bop}2.1。方法一:基于\verb|b&(b-1)|的运算，除去最末bit1。

\subsection{长内存块中bit1的个数}
\cite{pp}9.5.7\\
方法一：以字节或字为单位，统计每个单位中bit1的个数，再累加。方法二：查表法，对每个单位通过查表的方式获得1的个数，再累加。方法三：统计一个单位的取值分布，对于每个值出现对次数，乘以该值对应的1的个数。

\subsection{高效实现C语言isupper函数}
\cite{pp}9.5.6\\
使用一个256元的表(可以完全纳入缓存)，定义
\begin{verbatim}
#define isupper(c) (uppertable[c])
\end{verbatim}
大多数系统为表中每个元素存储几个bit，通过逻辑与操作来提取
\begin{verbatim}
#define isupper(c) (bigtable[c] & UPPER)
#define isalnum(c) (bigtable[c] & (UPPER|LOWER|DIGIT))
\end{verbatim}



\section{数论问题举例}

\subsection{最大公约数}
\cite{bop}2.7。\label{subsec:gcd}
方法0：欧几里德算法，辗转相除.
方法1：欧几里德算法减法版本，避免除法，但增加了减法.\verb|int gcd(i,j){while(i!=j){if(i>j)i-=j;else j-=i;}}|。
方法2：gcd初设为1。若两数均even，则均右移1位，gcd左移1位;若其一为even，则右移至成odd;若均为odd，则其一赋为两者差，必为even。通过最低bit快速判断奇偶性。


\subsection{自然数是否可表示为连续自然数之和}
\cite{bop}2.21。书上未给答案。可能答案是，只要不是2的幂，都可表示为连续自然数之和。可以通过试验数据找到规律并证明之。

\section{计算问题举例}

\subsection{桶计算}
将区间[0,n-1]中的若干整数按分布存放于m个桶(bin)中，计算若干整数应该放在哪个桶中(\cite{pp}13.6.9)，即整数值与单桶容量$n/m$做除法，t对应桶是$t/m*n$。如果保持桶数为m，将单桶容量近似提升为2的幂次$2^s \ge n/m > 2^{s-1},s=\lceil log_{m}{n} \rceil$，则可将乘除法局限于预处理过程，在实时计算桶号的过程只使用移位\verb|t>>s|。计算s的过程为，\verb|for(s=1;2^s < n/m;s++);|。循环在$2^s \ge n/m$时停止。

\subsection{计算浮点数均值}
\cite{pp}14.6.4.c, 11.5.1。两个差异较大的浮点数相加会产生精度问题。需要每次取集合中较小的两个数相加(类似于霍夫曼编码)，可以用优先级队列来完成。

\subsection{矩阵的幂}
\cite{bop}2.9提及，计算$A^n=A^{2} \cdot A^{4} \cdot A^{8}\dots$,时间复杂度为$O(logn)$。网上有说将矩阵相似对角化，可加速计算。
\label{matrixexpo}
\subsection{Fibonacci数列}
\cite{bop}2.9。方法一：求出通项公式。方法二：$(F_n,F_{n-1})=(F_{n-1},F_{n-2})\cdot A, A=  \left( \begin{array}{cc}1&1\\1&0\end{array}\right)$,进而转化为求$A^n$。

见\ref{matrixexpo}节。



\subsection{运算方式受限的连续自然数求和}
\cite{ms100}第12题。求$ \sum_{i=1}^{n}i $，不得使用乘除法、循环、和判断语句。方法：判断语句可用短路语句替代，固定循环可以展开，然而依赖
于变量的不定循环难以替代。根据$ \sum_{i=1}^{n}i = (n^{2}+n)<<1$，而$n^{2}=\sum_{k=0}^{32}I\{\textrm{n的第k位为1}\}(n<<k)$，循环展开即可。
\subsection{不定子向量频繁增减不定值}
\cite{pp}8.7.12。x[n]长度为n，并执行n次运算:\verb|x[l:u] += v|,其中l,u,v每次会变。该过程消耗平方时间。如果使用差分数组$diff[i]=x[i+1]-x[i]$,\verb|x[l:u] += v|转化为\verb|diff[l-1] += v, diff[u] -=v |，运算n次后再恢复出x，只需线性时间。

\subsection{除掉一个数，使剩余数乘积最大}
\cite{bop}2.13\\
要求不使用除法。方法一：根据所有数乘积为正、负、零三种情况讨论，会发现不需要进行任何运算，很容易可以得到解法。方法二：记数组长度为N，s[i]为前i个数乘积，t[j]为后j个数乘积，耗费O(N)的时间和空间能求出s，t两个数组，那么除去第k个数的所有数的乘积为s[k-1]t[N-k-1],总时间为线性。


\section{字符串问题举例}
\subsection{字符串循环右移K位}
\cite{bop}2.17,\cite{pp}2.1B。题目要求只允许两个附加变量。如无此要求，可以缓存最右K个元素。\\
如果K大于N，先取模，如果K大于N的一半，变换方向, K取作N-K。方法一：循环右移1位，执行K次。算法复杂度$O(N \cdot K)$，若K已被取模，算法复杂度$O(N^2)$。方法二：先整体旋转(线性时间)，再分别旋转左K个和右N-K个元素。方法三:\cite{pp}2.3,杂技算法。类似于希尔排序、图书馆排序的跳跃性移动,对内存不友好，编程复杂。方法四：Gries算法\cite{pp}2.6.3，中间不动交换两侧各K个数,然后去掉已经处于最终位置的K个数，递归，编程复杂。跟欧几里德算法版本\ref{subsec:gcd}是同构的。


\subsection{字符串移位包含问题}
\cite{bop}3.1。串A看作环形，是否包含串B。判断A+A是否包含B即可。


\subsection{词典聚类:变位词和电话键盘}
\cite{pp}2.4, 2.6.1。找出词典中所有互为变位词的集合，以及给定单词找出字典中所有它的变位词。词典中所有单词计算其标识，使得所有变位词具有相同标识。标识与单词构成元组，基于该标识对各元组排序，即可将所有变位词聚类。对于后一问题，可以按照前一个问题对各元组排序，执行词典预处理，这样就能使用二分搜索。实际系统往往使用散列技术或数据库系统(\cite{pp}2.6.6答案)。标识可以是单词内对字母按照字母表排序后形成的字符串。可以推广到对数据库中元组基于某规则进行归类。例如将将名字映射为拨号按键序列的问题(\cite{bop}3.2,\cite{pp}2.6.6, \cite{pie})求解所有映射成相同序列的名字，以及给定序列返回所有对应名字，此时标识就是按键序列。
\label{problem:dictClassify}

\subsection{字串枚举:电话号码对应英文单词}
\cite{bop}3.2, \cite{pie}P119\\
问题1：枚举一个电话号码能够构成的所有字母组合，普通枚举问题。问题2:基于词典，一个给定电话号码是否构成有意义的单词。方法一：基于问题1的解答，将每个答案同词典进行匹配，需要遍历词典很多次。方法二：将可以构成单词的电话号码预先存放到数字词典中。方法三:实质可看作词典聚类问题，参\ref{problem:dictClassify}，遍历一遍词典，判断每个单词是否符合这个电话号。
\label{question:phonekeyboard}

\subsection{文档词频统计}
\cite{pp}15.1。不基于词典，单词词形没有限制。利用散列表存储每个单词的词频，表的长度为质数29989，使哈希载荷因子接近1(圣经中有29121个单词，区分大小写)，用链表解决冲突。每次查询几乎为常数时间。总时间正比于文档长度。

\subsection{至少重复两次短语最大长度}
\cite{pp}15.2。此题没有单词的概念，只有字符。基于双指针同向扫描的算法需要平方时间。可以采用后缀数组，数组中每个元素为指针，指向文档中每个字符，相当于文档的每一个后缀都在数组中有所对应。然后基于对指针指向的字符串的比较，对后缀数组排序。扫描排序后的后缀数组，查看当前字符串与下一个字符串的共同前缀长度，找最大值。如果字符串比较的时间看作常数，那么总开销取决于排序，为线性乘以对数时间。然而，如果文档所有字符都一样，或者文档是由另一个文档复制了两次而来，那么字符串比较的时间和计算共同前缀的时间可能会正比于文档长度。

扩展:至少重复K次的最长短语(\cite{pp}15.5.8)。 同样对后缀数组排序，扫描后缀数组，查看当前字符串和后面第K-1个字符串的共同前缀长度，这两个字符串的共同前缀也是中间K-2个字符串的前缀，找最大值。

\label{problem:maxlenphrase}。

\subsection{K单词马尔可夫文本预测}
\cite{pp}15.3。基于当前位置K个单词预测下一个单词。在学习阶段，对训练文档，建立后缀数组(参\ref{problem:maxlenphrase})并排序，本题后缀数组的每个指针元素指向文档的各单词，而不是指向所有字符。同时，比较函数也改为，如果前K个单词相同则断定字符串相同)扫描后缀数组。在预测阶段，对于给定K单词短语，利用二分搜索在对数时间内定位到后缀数组中有相同K单词前缀的字符串(if any)，在这些字符串中随机选择一个，输出该字符串的下一个单词即可。作为优化(\cite{pp}15.5.8)，不对后缀数组进行排序，而是将每个后缀的位置存放在散列表中，使得具有相同K单词前缀的后缀在同一个散列表项中。这样，在预测阶段只用常数时间即可完成对给定短语的搜索。 


\subsection{最长公共子序列LCS}
算法导论动态规划章，子序列不需连续。

$LCS[x][y]= \left\{ \begin{array}{l} LCS[x-1][y-1]+1, A[x]=B[y] \\ max\{LCS[x][y-1], LCS[x-1][y]\}, A[X] \ne B[y] \end{array}  \right. $

\label{subsec:LCS}

\subsection{最长公共子字符串}
\cite{pp}15.5.9。与子字符\ref{subsec:LCS}的区别在于子串连续。将两个源字符串连接在一起，记录分隔点的位置，转换为求解最长重复短语的问题(\ref{problem:maxlenphrase})，区别在于扫描后缀数组时，如果当前后缀和下一个后缀出自相同的源字符串，则跳过。通过比较当前后缀对应的位置和分隔点的位置，可判断出该后缀出自哪个串。使用``异或''操作判断两个后缀是否出自同串。


\subsection{字符串相似度}
\cite{bop}3.3。相似度为最小的变换次数(记$\delta$, 单字符增、删、换)的倒数。
曾认为可先求LCS(\ref{subsec:LCS})，不妥。 简记A[x\ldots A.lenght-1]为A[x], 
\begin{displaymath}
   \delta(A[x], B[y])=
   \left\{
   \begin{array}{l}
       D[x+1][y+1], A[x]=B[y] \\ 
       min\{\delta[x][y+1], \delta[x][y+1], \delta[x+1][y+1] \}, A[y] \ne B[y]
   \end{array} 
    \right.
\end{displaymath}
\cite{bop}上程序写的大概是
\begin{math}
       min\{\delta[x+1][y+2], \delta[x+2][y+1], \delta[x+2][y+2] \}, A[y] \ne B[y]
\end{math}
,我认为不太正确。存在重复计算，可优化。

\subsection{包含所有关键词的最短摘要}
\cite{bop}3.5。枚举所有报文段($O(N^2)$)，枚举的过程中检查是否包含所有M个关键词($O(N^{2} \cdot M)$)。作为优化，\cite{bop}提出只考虑以关键词为开端的报文段。本题以搜索引擎为背景，个人认为不适合空间复杂度较高的算法，因此，不适合预处理报文，比如标记关键词在报文中的位置。检查任意报文分词是否为关键字的复杂度为$O(M)$。


\subsection{字符串中只出现一次的字符}
\cite{ms100}17。基于ASCII字符值域有限的特性，建立一长度255的数组，保存每个字符出现的次数。


\subsection{比特字符串排序}
\cite{pp}11.5.5。可变长位字符串排序，x[0\ldots n-1]每项包含整数length和指向数组bit[0\dots length-1]的指针，设bit[i]返回第i个bit的值(0或1)。 首先将长度小于递归深度的字符串移动到最左，再利用快速排序的Lomuto划分(参\ref{summary:quicksort})，将剩余部分划分成两部分，分布递归，检查下一位。

\begin{lstlisting}[language=C]
void bsort(l,u,depth)
    if l >= u return
    for i in [l, u]
	if x[i].length < depth
	    swap(i, l++)
    m = l
    for i in [l, u]
	if x[i].bit[depth] &=&  0
	    swap(i, m++)
    
    bsort(l, m-1, depth+1)
    bsort(m, u, depth+1)
\end{lstlisting}

一开始用bsort(0,n-1,1)调用该函数。运行时间正比与待排序数据量，即各字符串长度总和。swap移动的是字符串指针而非字符串本身。 \cite{self}认为该代码有误，除非bit的索引从1而非零开始。

\subsection{字符串排序}
\cite{self}待补充。




\section{杂问题举例}

\subsection{装箱问题的首次适应算法}
\cite{pp}14.6.5。
问题：将n个权值在(0,1)之间的数字分配到最少数目的单位容量箱。首次适应启发式算法按序考虑权值，按升序扫描箱，装入第一个合适的箱中。将箱组织成堆状结构，叶子结点为每个箱的剩余容量，其他结点的值为其子树中最空的箱的剩余容量。在选箱时，如果左右子树都合适，则选左树。选箱时间为对数，插入权值后沿插入路径更新剩余容量。

\subsection{日期计算}
\cite{pp}3.7.4，计算日期差、某天是周几以及为某月生成日历。历法常识参\ref{subsec:leapyear}。
日期差:基本思想是转换为各日期与相应元旦的差值，加上各元旦之间的差值。首先分别计算两个日期在所在年之内的编号，用后者减去前者，再加上年份差的365倍，再为每个闰年(包括起年，不包括止年)加1。求周几:需要计算给定日期和已知周日之间的天数，再做模运算。计算日历:需要知道该月1号为周几以及该月有多少天。

\subsection{大空间初始化避免}
\cite{pp}1.6.9。大数组data[0\dots n-1]需要初始化(如data[i]='a'+i\%26)，采取以空间换时间的即用即初始化策略回避对整个数组的初始化。开辟长度亦n的整数辅助数组history,eventNumber,变量top置0。检查data[i]是否已经初始化(访问过):\verb|if(0<=eventNumber[i]<top AND history[eventNumber[i]] is i)|。对data[i]的首次访问使用:\verb|eventNumber[i]=top;history[top]=i;init data[i];top++|，history数组记录初始化历史，依次指向各初始化事件的依此人。eventNumber[i]表示data[i]是第几例初始化(在history数组中的位置)。\label{problem:removeInit}

\subsection{区间[0,n-1]随机取出m个整数}

问题1:输出m个有序不重复整数(\cite{pp}12.5.8)。
方法1:候选空间遍历。(\cite{acp}3.4.2算法S，\cite{pp}12.2)\verb|s=m, r=n, for i in [0,n) { w.p.s/r{select i;s--;} r--;}|。该算法可保证如果r下降到同s相等则剩余候选数以概率1全部选中。时间同n成正比，当n很大时低效。$w.p.s/r$(with probability \verb|s/r|)实现为\verb|if (bigrand()%r < s)|。r和s分布代表select(剩余名额)和remaining(剩余候选集合)。
方法2：随机抽取,排序去重(\cite{pp}12.3)。可以使用C++ set模板类自动完成排序和去重，然后输出整个set。每次执行集合插入需要$O(logm)$，总时间$O(mlog m)$。如果使用其他数据结构\cite{self}，要求方便地实现排序和搜索，如BST，有序数组，有序链表。而heap不适合搜索，很难实现去重。Bob Floyd给出了改进(\cite{pp}12.5.9)，使得每次的抽样都不重复(第i次抽样空间为[0,i+n-m]，且如果同以往重复则取门限值i+n-m，高于往次门限，必不重复)。这样，不要求数据结构本身具有方便搜索的功能，只要便于排序即可，可以使用堆。
方法3：候选集合洗牌，头部排序。(\cite{pp}12.3)。\verb|for i in [0,n) x[i]=i; for j in [0,m) swap(j, rand(j,n-1)); sort(x,0,m);return x[0..m-1]|。空间复杂度正比于n，n很大时难以接受。初始化时间正比于n(可以避免，参\ref{problem:removeInit})，洗牌时间正比于m，排序时间$O(mlogm)$。

问题2:输出m个随机序不重复整数(\cite{pp}1.6.4)。
问题1方法3,去掉排序环节;方法2，改为排序前输出，即每次取样值(该值首次)插入数据结构时即输出，而不是输出数据结构,可用使用Floyd改进。

问题3:输出m个有序可重复整数(\cite{pp}12.5.8)。
问题1方法2, 选择集合之外的便于排序的数据结构(heap, BST, 有序数组，有序链表，C++ multimap)，抽取时不判断重复性，且不使用Floyd改进方案。

问题4:输出m个随机序可重复整数(\cite{pp}12.5.8)。
随机抽取，直接输出。问题3和4要求输出可重复整数，基于候选空间的算法不可用，只能基于抽取。








\subsection{枚举问题列表}
\begin{enumerate}
    \item 枚举一个电话号码能够构成的所有字母组合(\ref{question:phonekeyboard})
    \item 枚举目标字符串在源字符串中的连接次序，见\cite{pibible}8.2.1,P83
    \item 字符串的全排列，全组合
\end{enumerate}

















